/*
 This is rot.js, the ROguelike Toolkit in JavaScript.
 Version 0.3~dev, generated on Wed Dec  5 10:11:14 CET 2012.

 ** this version has been stripped down to just the map classes **
 */

/**
 * @namespace Top-level ROT namespace
 */
var ROT = {
    DEFAULT_WIDTH:80,
    DEFAULT_HEIGHT:25,

    /* Ordering is important! */
    DIRS:{
        "4":[
            [ 0, -1],
            [ 1, 0],
            [ 0, 1],
            [-1, 0]
        ],
        "8":[
            [ 0, -1],
            [ 1, -1],
            [ 1, 0],
            [ 1, 1],
            [ 0, 1],
            [-1, 1],
            [-1, 0],
            [-1, -1]
        ],
        "6":[
            [-1, -1],
            [ 1, -1],
            [ 2, 0],
            [ 1, 1],
            [-1, 1],
            [-2, 0]
        ]
    },

    /**
     * @returns {bool} Is rot.js supported by this browser?
     */
    isSupported:function () {
        return !!(document.createElement("canvas").getContext && Function.prototype.bind);
    }
};

/**
 * @returns {any} Randomly picked item, null when length=0
 */
Array.prototype.random = function () {
    if (!this.length) {
        return null;
    }
    return this[Math.floor(ROT.RNG.getUniform() * this.length)];
}

/**
 * @returns {array} Shallow copy
 */
Array.prototype.clone = function () {
    var arr = [];
    for (var i = 0; i < this.length; i++) {
        arr.push(this[i]);
    }
    return arr;
}

/**
 * @returns {array} New array with randomized items
 * FIXME destroys this!
 */
Array.prototype.randomize = function () {
    var result = [];
    while (this.length) {
        var index = this.indexOf(this.random());
        result.push(this.splice(index, 1)[0]);
    }
    return result;
}
if (!Date.now) {
    /**
     * @returns {int} Current timestamp (msec)
     */
    Date.now = function () {
        return +(new Date);
    }
}
/**
 * Always positive modulus
 * @param {int} n Modulus
 * @returns {int} this modulo n
 */
Number.prototype.mod = function (n) {
    return ((this % n) + n) % n;
}
/**
 * @returns {string} First letter capitalized
 */
String.prototype.capitalize = function () {
    return this.charAt(0).toUpperCase() + this.substring(1);
}

/**
 * @returns {string} This string with "%s"s replaced with arguments
 */
String.prototype.format = function () {
    var args = Array.prototype.slice.call(arguments);
    var str = this;
    return str.replace(/%s/g, function (match, index) {
        if (str.charAt(index - 1) == "%") {
            return match;
        } else {
            return args.shift();
        }
    });
}

/**
 * Left pad
 * @param {string} [character="0"]
 * @param {int} [count=2]
 */
String.prototype.lpad = function (character, count) {
    var ch = character || "0";
    var cnt = count || 2;

    var s = "";
    while (s.length < (cnt - this.length)) {
        s += ch;
    }
    s = s.substring(0, cnt - this.length);
    return s + this;
}

/**
 * Right pad
 * @param {string} [character="0"]
 * @param {int} [count=2]
 */
String.prototype.rpad = function (character, count) {
    var ch = character || "0";
    var cnt = count || 2;

    var s = "";
    while (s.length < (cnt - this.length)) {
        s += ch;
    }
    s = s.substring(0, cnt - this.length);
    return this + s;
}
if (!Object.create) {
    /**
     * ES5 Object.create
     */
    Object.create = function (o) {
        var tmp = function () {
        };
        tmp.prototype = o;
        return new tmp();
    };
}
/**
 * Sets prototype of this function to an instance of parent function
 * @param {function} parent
 */
Function.prototype.extend = function (parent) {
    this.prototype = Object.create(parent.prototype);
    this.prototype.constructor = this;
    return this;
}
/**
 * @namespace
 * This code is an implementation of Alea algorithm; (C) 2010 Johannes Baagøe.
 * Alea is licensed according to the http://en.wikipedia.org/wiki/MIT_License.
 */
ROT.RNG = {
    /**
     * @returns {number}
     */
    getSeed:function () {
        return this._seed;
    },

    /**
     * @param {number} seed Seed the number generator
     */
    setSeed:function (seed) {
        seed = (seed < 1 ? 1 / seed : seed);

        this._seed = seed;
        this._s0 = (seed >>> 0) * this._frac;

        seed = (seed * 69069 + 1) >>> 0;
        this._s1 = seed * this._frac;

        seed = (seed * 69069 + 1) >>> 0;
        this._s2 = seed * this._frac;

        this._c = 1;
        return this;
    },

    /**
     * @returns {float} Pseudorandom value [0,1), uniformly distributed
     */
    getUniform:function () {
        var t = 2091639 * this._s0 + this._c * this._frac;
        this._s0 = this._s1;
        this._s1 = this._s2;
        this._c = t | 0;
        this._s2 = t - this._c;
        return this._s2;
    },

    /**
     * @param {float} [mean=0] Mean value
     * @param {float} [stddev=1] Standard deviation. ~95% of the absolute values will be lower than 2*stddev.
     * @returns {float} A normally distributed pseudorandom value
     */
    getNormal:function (mean, stddev) {
        do {
            var u = 2 * this.getUniform() - 1;
            var v = 2 * this.getUniform() - 1;
            var r = u * u + v * v;
        } while (r > 1 || r == 0);

        var gauss = u * Math.sqrt(-2 * Math.log(r) / r);
        return (mean || 0) + gauss * (stddev || 1);
    },

    /**
     * @returns {int} Pseudorandom value [1,100] inclusive, uniformly distributed
     */
    getPercentage:function () {
        return 1 + Math.floor(this.getUniform() * 100);
    },

    /**
     * Get RNG state. Useful for storing the state and re-setting it via setState.
     * @returns {?} Internal state
     */
    getState:function () {
        return [this._s0, this._s1, this._s2, this._c];
    },

    /**
     * Set a previously retrieved state.
     * @param {?} state
     */
    setState:function (state) {
        this._s0 = state[0];
        this._s1 = state[1];
        this._s2 = state[2];
        this._c = state[3];
        return this;
    },

    _s0:0,
    _s1:0,
    _s2:0,
    _c:0,
    _frac:2.3283064365386963e-10 /* 2^-32 */
}

ROT.RNG.setSeed(Date.now());
/**
 * @class Base map generator
 * @param {int} [width=ROT.DEFAULT_WIDTH]
 * @param {int} [height=ROT.DEFAULT_HEIGHT]
 */
ROT.Map = function (width, height) {
    this._width = width || ROT.DEFAULT_WIDTH;
    this._height = height || ROT.DEFAULT_HEIGHT;
};

ROT.Map.prototype.create = function (callback) {
}

ROT.Map.prototype._fillMap = function (value) {
    var map = [];
    for (var i = 0; i < this._width; i++) {
        map.push([]);
        for (var j = 0; j < this._height; j++) {
            map[i].push(value);
        }
    }
    return map;
}
/**
 * @class Simple empty rectangular room
 * @augments ROT.Map
 */
ROT.Map.Arena = function (width, height) {
    ROT.Map.call(this, width, height);
}
ROT.Map.Arena.extend(ROT.Map);

ROT.Map.Arena.prototype.create = function (callback) {
    var w = this._width - 1;
    var h = this._height - 1;
    for (var i = 0; i <= w; i++) {
        for (var j = 0; j <= h; j++) {
            var empty = (i && j && i < w && j < h);
            callback(i, j, empty ? 0 : 1);
        }
    }
    return this;
}
/**
 * @class Recursively divided maze, http://en.wikipedia.org/wiki/Maze_generation_algorithm#Recursive_division_method
 * @augments ROT.Map
 */
ROT.Map.DividedMaze = function (width, height) {
    ROT.Map.call(this, width, height);
    this._stack = [];
}
ROT.Map.DividedMaze.extend(ROT.Map);

ROT.Map.DividedMaze.prototype.create = function (callback) {
    var w = this._width;
    var h = this._height;

    this._map = [];

    for (var i = 0; i < w; i++) {
        this._map.push([]);
        for (var j = 0; j < h; j++) {
            var border = (i == 0 || j == 0 || i + 1 == w || j + 1 == h);
            this._map[i].push(border ? 1 : 0);
        }
    }

    this._stack = [
        [1, 1, w - 2, h - 2]
    ];
    this._process();

    for (var i = 0; i < w; i++) {
        for (var j = 0; j < h; j++) {
            callback(i, j, this._map[i][j]);
        }
    }
    this._map = null;
    return this;
}

ROT.Map.DividedMaze.prototype._process = function () {
    while (this._stack.length) {
        var room = this._stack.shift();
        /* [left, top, right, bottom] */
        this._partitionRoom(room);
    }
}

ROT.Map.DividedMaze.prototype._partitionRoom = function (room) {
    var availX = [];
    var availY = [];

    for (var i = room[0] + 1; i < room[2]; i++) {
        var top = this._map[i][room[1] - 1];
        var bottom = this._map[i][room[3] + 1];
        if (top && bottom && !(i % 2)) {
            availX.push(i);
        }
    }

    for (var j = room[1] + 1; j < room[3]; j++) {
        var left = this._map[room[0] - 1][j];
        var right = this._map[room[2] + 1][j];
        if (left && right && !(j % 2)) {
            availY.push(j);
        }
    }

    if (!availX.length || !availY.length) {
        return;
    }

    var x = availX.random();
    var y = availY.random();

    this._map[x][y] = 1;

    var walls = [];

    var w = [];
    walls.push(w);
    /* left part */
    for (var i = room[0]; i < x; i++) {
        this._map[i][y] = 1;
        w.push([i, y]);
    }

    var w = [];
    walls.push(w);
    /* right part */
    for (var i = x + 1; i <= room[2]; i++) {
        this._map[i][y] = 1;
        w.push([i, y]);
    }

    var w = [];
    walls.push(w);
    /* top part */
    for (var j = room[1]; j < y; j++) {
        this._map[x][j] = 1;
        w.push([x, j]);
    }

    var w = [];
    walls.push(w);
    /* bottom part */
    for (var j = y + 1; j <= room[3]; j++) {
        this._map[x][j] = 1;
        w.push([x, j]);
    }

    var solid = walls.random();
    for (var i = 0; i < walls.length; i++) {
        var w = walls[i];
        if (w == solid) {
            continue;
        }

        var hole = w.random();
        this._map[hole[0]][hole[1]] = 0;
    }

    this._stack.push([room[0], room[1], x - 1, y - 1]);
    /* left top */
    this._stack.push([x + 1, room[1], room[2], y - 1]);
    /* right top */
    this._stack.push([room[0], y + 1, x - 1, room[3]]);
    /* left bottom */
    this._stack.push([x + 1, y + 1, room[2], room[3]]);
    /* right bottom */
}
/**
 * @class Icey's Maze generator
 * See http://www.roguebasin.roguelikedevelopment.org/index.php?title=Simple_maze for explanation
 * @augments ROT.Map
 */
ROT.Map.IceyMaze = function (width, height, regularity) {
    ROT.Map.call(this, width, height);
    this._regularity = regularity || 0;
}
ROT.Map.IceyMaze.extend(ROT.Map);

ROT.Map.IceyMaze.prototype.create = function (callback) {
    var width = this._width;
    var height = this._height;

    var map = this._fillMap(1);

    width -= (width % 2 ? 1 : 2);
    height -= (height % 2 ? 1 : 2);

    var cx = 0;
    var cy = 0;
    var nx = 0;
    var ny = 0;

    var done = 0;
    var blocked = false;
    var dirs = [
        [0, 0],
        [0, 0],
        [0, 0],
        [0, 0]
    ];
    do {
        cx = 1 + 2 * Math.floor(ROT.RNG.getUniform() * (width - 1) / 2);
        cy = 1 + 2 * Math.floor(ROT.RNG.getUniform() * (height - 1) / 2);

        if (!done) {
            map[cx][cy] = 0;
        }

        if (!map[cx][cy]) {
            this._randomize(dirs);
            do {
                if (Math.floor(ROT.RNG.getUniform() * (this._regularity + 1)) == 0) {
                    this._randomize(dirs);
                }
                blocked = true;
                for (var i = 0; i < 4; i++) {
                    nx = cx + dirs[i][0] * 2;
                    ny = cy + dirs[i][1] * 2;
                    if (this._isFree(map, nx, ny, width, height)) {
                        map[nx][ny] = 0;
                        map[cx + dirs[i][0]][cy + dirs[i][1]] = 0;

                        cx = nx;
                        cy = ny;
                        blocked = false;
                        done++;
                        break;
                    }
                }
            } while (!blocked);
        }
    } while (done + 1 < width * height / 4);

    for (var i = 0; i < this._width; i++) {
        for (var j = 0; j < this._height; j++) {
            callback(i, j, map[i][j]);
        }
    }
    this._map = null;
    return this;
}

ROT.Map.IceyMaze.prototype._randomize = function (dirs) {
    for (var i = 0; i < 4; i++) {
        dirs[i][0] = 0;
        dirs[i][1] = 0;
    }

    switch (Math.floor(ROT.RNG.getUniform() * 4)) {
        case 0:
            dirs[0][0] = -1;
            dirs[1][0] = 1;
            dirs[2][1] = -1;
            dirs[3][1] = 1;
            break;
        case 1:
            dirs[3][0] = -1;
            dirs[2][0] = 1;
            dirs[1][1] = -1;
            dirs[0][1] = 1;
            break;
        case 2:
            dirs[2][0] = -1;
            dirs[3][0] = 1;
            dirs[0][1] = -1;
            dirs[1][1] = 1;
            break;
        case 3:
            dirs[1][0] = -1;
            dirs[0][0] = 1;
            dirs[3][1] = -1;
            dirs[2][1] = 1;
            break;
    }
}

ROT.Map.IceyMaze.prototype._isFree = function (map, x, y, width, height) {
    if (x < 1 || y < 1 || x >= width || y >= height) {
        return false;
    }
    return map[x][y];
}
/**
 * @class Maze generator - Eller's algorithm
 * See http://homepages.cwi.nl/~tromp/maze.html for explanation
 * @augments ROT.Map
 */
ROT.Map.EllerMaze = function (width, height) {
    ROT.Map.call(this, width, height);
}
ROT.Map.EllerMaze.extend(ROT.Map);

ROT.Map.EllerMaze.prototype.create = function (callback) {
    var map = this._fillMap(1);
    var w = Math.ceil((this._width - 2) / 2);

    var rand = 9 / 24;

    var L = [];
    var R = [];

    for (var i = 0; i < w; i++) {
        L.push(i);
        R.push(i);
    }
    L.push(w - 1);
    /* fake stop-block at the right side */

    for (var j = 1; j + 3 < this._height; j += 2) {
        /* one row */
        for (var i = 0; i < w; i++) {
            /* cell coords (will be always empty) */
            var x = 2 * i + 1;
            var y = j;
            map[x][y] = 0;

            /* right connection */
            if (i != L[i + 1] && ROT.RNG.getUniform() > rand) {
                this._addToList(i, L, R);
                map[x + 1][y] = 0;
            }

            /* bottom connection */
            if (i != L[i] && ROT.RNG.getUniform() > rand) {
                /* remove connection */
                this._removeFromList(i, L, R);
            } else {
                /* create connection */
                map[x][y + 1] = 0;
            }
        }
    }

    /* last row */
    for (var i = 0; i < w; i++) {
        /* cell coords (will be always empty) */
        var x = 2 * i + 1;
        var y = j;
        map[x][y] = 0;

        /* right connection */
        if (i != L[i + 1] && (i == L[i] || ROT.RNG.getUniform() > rand)) {
            /* dig right also if the cell is separated, so it gets connected to the rest of maze */
            this._addToList(i, L, R);
            map[x + 1][y] = 0;
        }

        this._removeFromList(i, L, R);
    }

    for (var i = 0; i < this._width; i++) {
        for (var j = 0; j < this._height; j++) {
            callback(i, j, map[i][j]);
        }
    }

    return this;
}

/**
 * Remove "i" from its list
 */
ROT.Map.EllerMaze.prototype._removeFromList = function (i, L, R) {
    R[L[i]] = R[i];
    L[R[i]] = L[i];
    R[i] = i;
    L[i] = i;
}

/**
 * Join lists with "i" and "i+1"
 */
ROT.Map.EllerMaze.prototype._addToList = function (i, L, R) {
    R[L[i + 1]] = R[i];
    L[R[i]] = L[i + 1];
    R[i] = i + 1;
    L[i + 1] = i;
}
/**
 * @class Cellular automaton map generator
 * @augments ROT.Map
 * @param {int} [width=ROT.DEFAULT_WIDTH]
 * @param {int} [height=ROT.DEFAULT_HEIGHT]
 * @param {object} [options] Options
 * @param {int[]} [options.born] List of neighbor counts for a new cell to be born in empty space
 * @param {int[]} [options.survive] List of neighbor counts for an existing  cell to survive
 * @param {int} [options.topology] Topology 4 or 6 or 8
 */
ROT.Map.Cellular = function (width, height, options) {
    ROT.Map.call(this, width, height);
    this._options = {
        born:[5, 6, 7, 8],
        survive:[4, 5, 6, 7, 8],
        topology:8
    };
    for (var p in options) {
        this._options[p] = options[p];
    }

    this._dirs = ROT.DIRS[this._options.topology];
    this._map = this._fillMap(0);
}
ROT.Map.Cellular.extend(ROT.Map);

/**
 * Fill the map with random values
 * @param {float} probability Probability for a cell to become alive; 0 = all empty, 1 = all full
 */
ROT.Map.Cellular.prototype.randomize = function (probability) {
    for (var i = 0; i < this._width; i++) {
        for (var j = 0; j < this._height; j++) {
            this._map[i][j] = (ROT.RNG.getUniform() < probability ? 1 : 0);
        }
    }
}

ROT.Map.Cellular.prototype.set = function (x, y, value) {
    this._map[x][y] = value;
}

ROT.Map.Cellular.prototype.create = function (callback) {
    var newMap = this._fillMap(0);
    var born = this._options.born;
    var survive = this._options.survive;


    for (var j = 0; j < this._height; j++) {
        var widthStep = 1;
        var widthStart = 0;
        if (this._options.topology == 6) {
            widthStep = 2;
            widthStart = j % 2;
        }

        for (var i = widthStart; i < this._width; i += widthStep) {

            var cur = this._map[i][j];
            var ncount = this._getNeighbors(i, j);

            if (cur && survive.indexOf(ncount) != -1) { /* survive */
                newMap[i][j] = 1;
            } else if (!cur && born.indexOf(ncount) != -1) { /* born */
                newMap[i][j] = 1;
            }

            if (callback) {
                callback(i, j, newMap[i][j]);
            }
        }
    }

    this._map = newMap;
}

/**
 * Get neighbor count at [i,j] in this._map
 */
ROT.Map.Cellular.prototype._getNeighbors = function (cx, cy) {
    var result = 0;
    for (var i = 0; i < this._dirs.length; i++) {
        var dir = this._dirs[i];
        var x = cx + dir[0];
        var y = cy + dir[1];

        if (x < 0 || x >= this._width || x < 0 || y >= this._width) {
            continue;
        }
        result += (this._map[x][y] == 1 ? 1 : 0);
    }

    return result;
}
/**
 * @class Dungeon map: has rooms and corridors
 * @augments ROT.Map
 */
ROT.Map.Dungeon = function (width, height) {
    ROT.Map.call(this, width, height);
    this._rooms = [];
    /* list of all rooms */
    this._corridors = [];
}
ROT.Map.Dungeon.extend(ROT.Map);

/**
 * Get all generated rooms
 * @returns {ROT.Map.Feature.Room[]}
 */
ROT.Map.Dungeon.prototype.getRooms = function () {
    return this._rooms;
}

/**
 * Get all generated corridors
 * @returns {ROT.Map.Feature.Corridor[]}
 */
ROT.Map.Dungeon.prototype.getCorridors = function () {
    return this._corridors;
}
/**
 * @class Random dungeon generator using human-like digging patterns.
 * Heavily based on Mike Anderson's ideas from the "Tyrant" algo, mentioned at
 * http://www.roguebasin.roguelikedevelopment.org/index.php?title=Dungeon-Building_Algorithm.
 * @augments ROT.Map.Dungeon
 */
ROT.Map.Digger = function (width, height, options) {
    ROT.Map.Dungeon.call(this, width, height);
    console.log("options", options);
    this._options = {
        roomWidth:[3, 9], /* room minimum and maximum width */
        roomHeight:[3, 5], /* room minimum and maximum height */
        corridorLength:[3, 10], /* corridor minimum and maximum length */
        dugPercentage:0.2, /* we stop after this percentage of level area has been dug out */
        timeLimit:1000 /* we stop after this much time has passed (msec) */
    }
    for (var p in options) {
        this._options[p] = options[p];
    }

    this._features = {
        "Room":4,
        "Corridor":4
    }
    this._featureAttempts = 20;
    /* how many times do we try to create a feature on a suitable wall */
    this._walls = {};
    /* these are available for digging */

    this._digCallback = this._digCallback.bind(this);
    this._canBeDugCallback = this._canBeDugCallback.bind(this);
    this._isWallCallback = this._isWallCallback.bind(this);
    this._priorityWallCallback = this._priorityWallCallback.bind(this);
}
ROT.Map.Digger.extend(ROT.Map.Dungeon);

/**
 * Create a map
 * @see ROT.Map#create
 */
ROT.Map.Digger.prototype.create = function (callback) {
    this._rooms = [];
    this._corridors = [];
    this._map = this._fillMap(1);
    this._walls = {};
    this._dug = 0;
    var area = (this._width - 2) * (this._height - 2);

    this._firstRoom();

    var t1 = Date.now();

    do {
        var t2 = Date.now();
        if (t2 - t1 > this._options.timeLimit) {
            break;
        }

        /* find a good wall */
        var wall = this._findWall();
        if (!wall) {
            break;
        }
        /* no more walls */

        var parts = wall.split(",");
        var x = parseInt(parts[0]);
        var y = parseInt(parts[1]);
        var dir = this._getDiggingDirection(x, y);
        if (!dir) {
            continue;
        }
        /* this wall is not suitable */

    	console.log("wall", x, y);

        /* try adding a feature */
        var featureAttempts = 0;
        do {
            featureAttempts++;
            if (this._tryFeature(x, y, dir[0], dir[1])) { /* feature added */
                if (this._rooms.length + this._corridors.length == 2) {
                    this._rooms[0].addDoor(x, y);
                }
                /* first room oficially has doors */
                this._removeSurroundingWalls(x, y);
                this._removeSurroundingWalls(x - dir[0], y - dir[1]);
                break;
            }
        } while (featureAttempts < this._featureAttempts);

        var priorityWalls = 0;
        for (var id in this._walls) {
            if (this._walls[id] > 1) {
                priorityWalls++;
            }
        }

    } while (this._dug / area < this._options.dugPercentage || priorityWalls);
    /* fixme number of priority walls */

    if (callback) {
        for (var i = 0; i < this._width; i++) {
            for (var j = 0; j < this._height; j++) {
                callback(i, j, this._map[i][j]);
            }
        }
    }

    this._walls = {};
    this._map = null;

    return this;
}

ROT.Map.Digger.prototype._digCallback = function (x, y, value) {
    if (value == 0 || value == 2) { /* empty */
        this._map[x][y] = 0;
        this._dug++;
    } else { /* wall */
        this._walls[x + "," + y] = 1;
    }
}

ROT.Map.Digger.prototype._isWallCallback = function (x, y) {
    if (x < 0 || y < 0 || x >= this._width || y >= this._height) {
        return false;
    }
    return (this._map[x][y] == 1);
}

ROT.Map.Digger.prototype._canBeDugCallback = function (x, y) {
    if (x < 1 || y < 1 || x + 1 >= this._width || y + 1 >= this._height) {
        return false;
    }
    return (this._map[x][y] == 1);
}

ROT.Map.Digger.prototype._priorityWallCallback = function (x, y) {
    this._walls[x + "," + y] = 2;
}

ROT.Map.Digger.prototype._firstRoom = function () {
    var cx = Math.floor(this._width / 2);
    var cy = Math.floor(this._height / 2);
    var room = ROT.Map.Feature.Room.createRandomCenter(cx, cy, this._options);
    this._rooms.push(room);
    room.create(this._digCallback);
}

/**
 * Get a suitable wall
 */
ROT.Map.Digger.prototype._findWall = function () {
    var prio1 = [];
    var prio2 = [];
    for (var id in this._walls) {
        var prio = this._walls[id];
        if (prio == 2) {
            prio2.push(id);
        } else {
            prio1.push(id);
        }
    }

    var arr = (prio2.length ? prio2 : prio1);
    if (!arr.length) {
        return null;
    }
    /* no walls :/ */

    var id = arr.random();
    delete this._walls[id];

    return id;
}

/**
 * Tries adding a feature
 * @returns {bool} was this a successful try?
 */
ROT.Map.Digger.prototype._tryFeature = function (x, y, dx, dy) {
    var feature = null;
    var total = 0;
    for (var p in this._features) {
        total += this._features[p];
    }
    var random = Math.floor(ROT.RNG.getUniform() * total);

    var sub = 0;
    for (var p in this._features) {
        sub += this._features[p];
        if (random < sub) {
            feature = ROT.Map.Feature[p];
            break;
        }
    }

    feature = feature.createRandomAt(x, y, dx, dy, this._options);

    if (!feature.isValid(this._isWallCallback, this._canBeDugCallback)) {
//		console.log("not valid");
//		feature.debug();
        return false;
    }

    feature.create(this._digCallback);
//	feature.debug();

    if (feature instanceof ROT.Map.Feature.Room) {
        this._rooms.push(feature);
    }
    if (feature instanceof ROT.Map.Feature.Corridor) {
        feature.createPriorityWalls(this._priorityWallCallback);
        this._corridors.push(feature);
    }

    return true;
}

ROT.Map.Digger.prototype._removeSurroundingWalls = function (cx, cy) {
    var deltas = ROT.DIRS[4];

    for (var i = 0; i < deltas.length; i++) {
        var delta = deltas[i];
        var x = cx + delta[0];
        var y = cy + delta[1];
        delete this._walls[x + "," + y];
        var x = cx + 2 * delta[0];
        var y = cy + 2 * delta[1];
        delete this._walls[x + "," + y];
    }
}

/**
 * Returns vector in "digging" direction, or false, if this does not exist (or is not unique)
 */
ROT.Map.Digger.prototype._getDiggingDirection = function (cx, cy) {
    var result = null;
    var deltas = ROT.DIRS[4];

    for (var i = 0; i < deltas.length; i++) {
        var delta = deltas[i];
        var x = cx + delta[0];
        var y = cy + delta[1];

        if (x < 0 || y < 0 || x >= this._width || y >= this._width) {
            return null;
        }

        if (!this._map[x][y]) { /* there already is another empty neighbor! */
            if (result) {
                return null;
            }
            result = delta;
        }
    }

    /* no empty neighbor */
    if (!result) {
        return null;
    }

    return [-result[0], -result[1]];
}
/**
 * @class Dungeon generator which tries to fill the space evenly. Generates independent rooms and tries to connect them.
 * @augments ROT.Map.Dungeon
 */
ROT.Map.Uniform = function (width, height, options) {
    ROT.Map.Dungeon.call(this, width, height);

    this._options = {
        roomWidth:[3, 9], /* room minimum and maximum width */
        roomHeight:[3, 5], /* room minimum and maximum height */
        roomDugPercentage:0.1, /* we stop after this percentage of level area has been dug out by rooms */
        timeLimit:1000 /* we stop after this much time has passed (msec) */
    }
    for (var p in options) {
        this._options[p] = options[p];
    }

    this._roomAttempts = 20;
    /* new room is created N-times until is considered as impossible to generate */
    this._corridorAttempts = 20;
    /* corridors are tried N-times until the level is considered as impossible to connect */

    this._connected = [];
    /* list of already connected rooms */
    this._unconnected = [];
    /* list of remaining unconnected rooms */

    this._digCallback = this._digCallback.bind(this);
    this._canBeDugCallback = this._canBeDugCallback.bind(this);
    this._isWallCallback = this._isWallCallback.bind(this);
}
ROT.Map.Uniform.extend(ROT.Map.Dungeon);

/**
 * Create a map. If the time limit has been hit, returns null.
 * @see ROT.Map#create
 */
ROT.Map.Uniform.prototype.create = function (callback) {
    var t1 = Date.now();
    while (1) {
        var t2 = Date.now();
        if (t2 - t1 > this._options.timeLimit) {
            return null;
        }
        /* time limit! */

        this._map = this._fillMap(1);
        this._dug = 0;
        this._rooms = [];
        this._unconnected = [];
        this._generateRooms();
        if (this._generateCorridors()) {
            break;
        }
    }

    if (callback) {
        for (var i = 0; i < this._width; i++) {
            for (var j = 0; j < this._height; j++) {
                callback(i, j, this._map[i][j]);
            }
        }
    }

    return this;
}

/**
 * Generates a suitable amount of rooms
 */
ROT.Map.Uniform.prototype._generateRooms = function () {
    var w = this._width - 2;
    var h = this._height - 2;

    do {
        var room = this._generateRoom();
        if (this._dug / (w * h) > this._options.roomDugPercentage) {
            break;
        }
        /* achieved requested amount of free space */
    } while (room);

    /* either enough rooms, or not able to generate more of them :) */
}

/**
 * Try to generate one room
 */
ROT.Map.Uniform.prototype._generateRoom = function () {
    var count = 0;
    while (count < this._roomAttempts) {
        count++;

        var room = ROT.Map.Feature.Room.createRandom(this._width, this._height, this._options);
        if (!room.isValid(this._isWallCallback, this._canBeDugCallback)) {
            continue;
        }

        room.create(this._digCallback);
        this._rooms.push(room);
        return room;
    }

    /* no room was generated in a given number of attempts */
    return null;
}

/**
 * Generates connectors beween rooms
 * @returns {bool} success Was this attempt successfull?
 */
ROT.Map.Uniform.prototype._generateCorridors = function () {
    var cnt = 0;
    while (cnt < this._corridorAttempts) {
        cnt++;
        this._corridors = [];

        /* dig rooms into a clear map */
        this._map = this._fillMap(1);
        for (var i = 0; i < this._rooms.length; i++) {
            var room = this._rooms[i];
            room.clearDoors();
            room.create(this._digCallback);
        }

        this._unconnected = this._rooms.clone().randomize();
        this._connected = [];
        if (this._unconnected.length) {
            this._connected.push(this._unconnected.pop());
        }
        /* first one is always connected */

        while (1) {
            /* 1. pick random connected room */
            var connected = this._connected.random();

            /* 2. find closest unconnected */
            var room1 = this._closestRoom(this._unconnected, connected);

            /* 3. connect it to closest connected */
            var room2 = this._closestRoom(this._connected, room1);

            var ok = this._connectRooms(room1, room2);
            if (!ok) {
                break;
            }
            /* stop connecting, re-shuffle */

            if (!this._unconnected.length) {
                return true;
            }
            /* done; no rooms remain */
        }
    }
    return false;
}

/**
 * For a given room, find the closest one from the list
 */
ROT.Map.Uniform.prototype._closestRoom = function (rooms, room) {
    var dist = Infinity;
    var center = room.getCenter();
    var result = null;

    for (var i = 0; i < rooms.length; i++) {
        var r = rooms[i];
        var c = r.getCenter();
        var dx = c[0] - center[0];
        var dy = c[1] - center[1];
        var d = dx * dx + dy * dy;

        if (d < dist) {
            dist = d;
            result = r;
        }
    }

    return result;
}

ROT.Map.Uniform.prototype._connectRooms = function (room1, room2) {
    /*
     room1.debug();
     room2.debug();
     */

    var center1 = room1.getCenter();
    var center2 = room2.getCenter();

    var diffX = center2[0] - center1[0];
    var diffY = center2[1] - center1[1];

    if (Math.abs(diffX) < Math.abs(diffY)) { /* first try connecting north-south walls */
        var dirIndex1 = (diffY > 0 ? 2 : 0);
        var dirIndex2 = (dirIndex1 + 2) % 4;
        var min = room2.getLeft();
        var max = room2.getRight();
        var index = 0;
    } else { /* first try connecting east-west walls */
        var dirIndex1 = (diffX > 0 ? 1 : 3);
        var dirIndex2 = (dirIndex1 + 2) % 4;
        var min = room2.getTop();
        var max = room2.getBottom();
        var index = 1;
    }

    var start = this._placeInWall(room1, dirIndex1);
    /* corridor will start here */
    if (!start) {
        return false;
    }

    if (start[index] >= min && start[index] <= max) { /* possible to connect with straight line (I-like) */
        var end = start.clone();
        var value = null;
        switch (dirIndex2) {
            case 0:
                value = room2.getTop() - 1;
                break;
            case 1:
                value = room2.getRight() + 1;
                break;
            case 2:
                value = room2.getBottom() + 1;
                break;
            case 3:
                value = room2.getLeft() - 1;
                break;
        }
        end[(index + 1) % 2] = value;
        this._digLine([start, end]);

    } else if (start[index] < min - 1 || start[index] > max + 1) { /* need to switch target wall (L-like) */

        var diff = start[index] - center2[index];
        switch (dirIndex2) {
            case 0:
            case 1:
                var rotation = (diff < 0 ? 3 : 1);
                break;
            case 2:
            case 3:
                var rotation = (diff < 0 ? 1 : 3);
                break;
        }
        dirIndex2 = (dirIndex2 + rotation) % 4;

        var end = this._placeInWall(room2, dirIndex2);
        if (!end) {
            return false;
        }

        var mid = [0, 0];
        mid[index] = start[index];
        var index2 = (index + 1) % 2;
        mid[index2] = end[index2];
        this._digLine([start, mid, end]);

    } else { /* use current wall pair, but adjust the line in the middle (S-like) */

        var index2 = (index + 1) % 2;
        var end = this._placeInWall(room2, dirIndex2);
        if (!end) {
            return;
        }
        var mid = Math.round((end[index2] + start[index2]) / 2);

        var mid1 = [0, 0];
        var mid2 = [0, 0];
        mid1[index] = start[index];
        mid1[index2] = mid;
        mid2[index] = end[index];
        mid2[index2] = mid;
        this._digLine([start, mid1, mid2, end]);
    }

    room1.addDoor(start[0], start[1]);
    room2.addDoor(end[0], end[1]);

    var index = this._unconnected.indexOf(room1);
    if (index != -1) {
        this._unconnected.splice(index, 1);
        this._connected.push(room1);
    }

    var index = this._unconnected.indexOf(room2);
    if (index != -1) {
        this._unconnected.splice(index, 1);
        this._connected.push(room2);
    }

    return true;
}

ROT.Map.Uniform.prototype._placeInWall = function (room, dirIndex) {
    var start = [0, 0];
    var dir = [0, 0];
    var length = 0;

    switch (dirIndex) {
        case 0:
            dir = [1, 0];
            start = [room.getLeft(), room.getTop() - 1];
            length = room.getRight() - room.getLeft() + 1;
            break;
        case 1:
            dir = [0, 1];
            start = [room.getRight() + 1, room.getTop()];
            length = room.getBottom() - room.getTop() + 1;
            break;
        case 2:
            dir = [1, 0];
            start = [room.getLeft(), room.getBottom() + 1];
            length = room.getRight() - room.getLeft() + 1;
            break;
        case 3:
            dir = [0, 1];
            start = [room.getLeft() - 1, room.getTop()];
            length = room.getBottom() - room.getTop() + 1;
            break;
    }

    var avail = [];
    var lastBadIndex = -2;

    for (var i = 0; i < length; i++) {
        var x = start[0] + i * dir[0];
        var y = start[1] + i * dir[1];
        avail.push(null);

        var isWall = (this._map[x][y] == 1);
        if (isWall) {
            if (lastBadIndex != i - 1) {
                avail[i] = [x, y];
            }
        } else {
            lastBadIndex = i;
            if (i) {
                avail[i - 1] = null;
            }
        }
    }

    for (var i = avail.length - 1; i >= 0; i--) {
        if (!avail[i]) {
            avail.splice(i, 1);
        }
    }
    return (avail.length ? avail.random() : null);
}

/**
 * Dig a polyline.
 */
ROT.Map.Uniform.prototype._digLine = function (points) {
    for (var i = 1; i < points.length; i++) {
        var start = points[i - 1];
        var end = points[i];
        var corridor = new ROT.Map.Feature.Corridor(start[0], start[1], end[0], end[1]);
        corridor.create(this._digCallback);
        this._corridors.push(corridor);
    }
}

ROT.Map.Uniform.prototype._digCallback = function (x, y, value) {
    this._map[x][y] = value;
    if (value == 0) {
        this._dug++;
    }
}

ROT.Map.Uniform.prototype._isWallCallback = function (x, y) {
    if (x < 0 || y < 0 || x >= this._width || y >= this._height) {
        return false;
    }
    return (this._map[x][y] == 1);
}

ROT.Map.Uniform.prototype._canBeDugCallback = function (x, y) {
    if (x < 1 || y < 1 || x + 1 >= this._width || y + 1 >= this._height) {
        return false;
    }
    return (this._map[x][y] == 1);
}

/**
 * @class
 * Dungeon feature; has own .create() method
 */
ROT.Map.Feature = function () {
}
ROT.Map.Feature.prototype.isValid = function (canBeDugCallback) {
}
ROT.Map.Feature.prototype.create = function (digCallback) {
}
ROT.Map.Feature.prototype.debug = function () {
}
ROT.Map.Feature.createRandomAt = function (x, y, dx, dy, options) {
}

/**
 * @class Room
 * @augments ROT.Map.Feature
 * @param {int} x1
 * @param {int} y1
 * @param {int} x2
 * @param {int} y2
 * @param {int} [doorX]
 * @param {int} [doorY]
 */
ROT.Map.Feature.Room = function (x1, y1, x2, y2, doorX, doorY) {
    this._x1 = x1;
    this._y1 = y1;
    this._x2 = x2;
    this._y2 = y2;
    this._doors = {};
    if (arguments.length > 4) {
        this.addDoor(doorX, doorY);
    }
}
ROT.Map.Feature.Room.extend(ROT.Map.Feature);

/**
 * Room of random size, with a given doors and direction
 */
ROT.Map.Feature.Room.createRandomAt = function (x, y, dx, dy, options) {
    var min = options.roomWidth[0];
    var max = options.roomWidth[1];
    var width = min + Math.floor(ROT.RNG.getUniform() * (max - min + 1));

    var min = options.roomHeight[0];
    var max = options.roomHeight[1];
    var height = min + Math.floor(ROT.RNG.getUniform() * (max - min + 1));

    if (dx == 1) { /* to the right */
        var y2 = y - Math.floor(ROT.RNG.getUniform() * height);
        return new this(x + 1, y2, x + width, y2 + height - 1, x, y);
    }

    if (dx == -1) { /* to the left */
        var y2 = y - Math.floor(ROT.RNG.getUniform() * height);
        return new this(x - width, y2, x - 1, y2 + height - 1, x, y);
    }

    if (dy == 1) { /* to the bottom */
        var x2 = x - Math.floor(ROT.RNG.getUniform() * width);
        return new this(x2, y + 1, x2 + width - 1, y + height, x, y);
    }

    if (dy == -1) { /* to the top */
        var x2 = x - Math.floor(ROT.RNG.getUniform() * width);
        return new this(x2, y - height, x2 + width - 1, y - 1, x, y);
    }
}

/**
 * Room of random size, positioned around center coords
 */
ROT.Map.Feature.Room.createRandomCenter = function (cx, cy, options) {
    var min = options.roomWidth[0];
    var max = options.roomWidth[1];
    var width = min + Math.floor(ROT.RNG.getUniform() * (max - min + 1));

    var min = options.roomHeight[0];
    var max = options.roomHeight[1];
    var height = min + Math.floor(ROT.RNG.getUniform() * (max - min + 1));

    var x1 = cx - Math.floor(ROT.RNG.getUniform() * width);
    var y1 = cy - Math.floor(ROT.RNG.getUniform() * height);
    var x2 = x1 + width - 1;
    var y2 = y1 + height - 1;

    return new this(x1, y1, x2, y2);
}

/**
 * Room of random size within a given dimensions
 */
ROT.Map.Feature.Room.createRandom = function (availWidth, availHeight, options) {
    var min = options.roomWidth[0];
    var max = options.roomWidth[1];
    var width = min + Math.floor(ROT.RNG.getUniform() * (max - min + 1));

    var min = options.roomHeight[0];
    var max = options.roomHeight[1];
    var height = min + Math.floor(ROT.RNG.getUniform() * (max - min + 1));

    var left = availWidth - width - 1;
    var top = availHeight - height - 1;

    var x1 = 1 + Math.floor(ROT.RNG.getUniform() * left);
    var y1 = 1 + Math.floor(ROT.RNG.getUniform() * top);
    var x2 = x1 + width - 1;
    var y2 = y1 + height - 1;

    return new this(x1, y1, x2, y2);
}

ROT.Map.Feature.Room.prototype.addDoor = function (x, y) {
    this._doors[x + "," + y] = 1;
}

ROT.Map.Feature.Room.prototype.clearDoors = function () {
    this._doors = {};
    return this;
}

ROT.Map.Feature.Room.prototype.debug = function () {
    console.log("room", this._x1, this._y1, this._x2, this._y2);
}

ROT.Map.Feature.Room.prototype.isValid = function (isWallCallback, canBeDugCallback) {
    var left = this._x1 - 1;
    var right = this._x2 + 1;
    var top = this._y1 - 1;
    var bottom = this._y2 + 1;

    for (var x = left; x <= right; x++) {
        for (var y = top; y <= bottom; y++) {
            if (x == left || x == right || y == top || y == bottom) {
                if (!isWallCallback(x, y)) {
                    return false;
                }
            } else {
                if (!canBeDugCallback(x, y)) {
                    return false;
                }
            }
        }
    }

    return true;
}

/**
 * @param {function} digCallback Dig callback with a signature (x, y, value). Values: 0 = empty, 1 = wall, 2 = door. Multiple doors are allowed.
 */
ROT.Map.Feature.Room.prototype.create = function (digCallback) {
    var left = this._x1 - 1;
    var right = this._x2 + 1;
    var top = this._y1 - 1;
    var bottom = this._y2 + 1;

    var value = 0;
    for (var x = left; x <= right; x++) {
        for (var y = top; y <= bottom; y++) {
            if (x + "," + y in this._doors) {
                value = 2;
            } else if (x == left || x == right || y == top || y == bottom) {
                value = 1;
            } else {
                value = 0;
            }
            digCallback(x, y, value);
        }
    }
}

ROT.Map.Feature.Room.prototype.getCenter = function () {
    return [Math.round((this._x1 + this._x2) / 2), Math.round((this._y1 + this._y2) / 2)];
}

ROT.Map.Feature.Room.prototype.getLeft = function () {
    return this._x1;
}

ROT.Map.Feature.Room.prototype.getRight = function () {
    return this._x2;
}

ROT.Map.Feature.Room.prototype.getTop = function () {
    return this._y1;
}

ROT.Map.Feature.Room.prototype.getBottom = function () {
    return this._y2;
}

/**
 * @class Corridor
 * @augments ROT.Map.Feature
 * @param {int} startX
 * @param {int} startY
 * @param {int} endX
 * @param {int} endY
 */
ROT.Map.Feature.Corridor = function (startX, startY, endX, endY) {
    this._startX = startX;
    this._startY = startY;
    this._endX = endX;
    this._endY = endY;
    this._endsWithAWall = true;
}
ROT.Map.Feature.Corridor.extend(ROT.Map.Feature);

ROT.Map.Feature.Corridor.createRandomAt = function (x, y, dx, dy, options) {
    var min = options.corridorLength[0];
    var max = options.corridorLength[1];
    var length = min + Math.floor(ROT.RNG.getUniform() * (max - min + 1));

    return new this(x, y, x + dx * length, y + dy * length);
}

ROT.Map.Feature.Corridor.prototype.debug = function () {
    console.log("corridor", this._startX, this._startY, this._endX, this._endY);
}

ROT.Map.Feature.Corridor.prototype.isValid = function (isWallCallback, canBeDugCallback) {
    var sx = this._startX;
    var sy = this._startY;
    var dx = this._endX - sx;
    var dy = this._endY - sy;
    var length = 1 + Math.max(Math.abs(dx), Math.abs(dy));

    if (dx) {
        dx = dx / Math.abs(dx);
    }
    if (dy) {
        dy = dy / Math.abs(dy);
    }
    var nx = dy;
    var ny = -dx;

    var ok = true;
    for (var i = 0; i < length; i++) {
        var x = sx + i * dx;
        var y = sy + i * dy;

        if (!canBeDugCallback(x, y)) {
            ok = false;
        }
        if (!isWallCallback(x + nx, y + ny)) {
            ok = false;
        }
        if (!isWallCallback(x - nx, y - ny)) {
            ok = false;
        }

        if (!ok) {
            length = i;
            this._endX = x - dx;
            this._endY = y - dy;
            break;
        }
    }

    /**
     * If the length degenerated, this corridor might be invalid
     */

    /* not supported */
    if (length == 0) {
        return false;
    }

    /* length 1 allowed only if the next space is empty */
    if (length == 1 && isWallCallback(this._endX + dx, this._endY + dy)) {
        return false;
    }

    /**
     * We do not want the corridor to crash into a corner of a room;
     * if any of the ending corners is empty, the N+1th cell of this corridor must be empty too.
     *
     * Situation:
     * #######1
     * .......?
     * #######2
     *
     * The corridor was dug from left to right.
     * 1, 2 - problematic corners, ? = N+1th cell (not dug)
     */
    var firstCornerBad = !isWallCallback(this._endX + dx + nx, this._endY + dy + ny);
    var secondCornerBad = !isWallCallback(this._endX + dx - nx, this._endY + dy - ny);
    this._endsWithAWall = isWallCallback(this._endX + dx, this._endY + dy);
    if ((firstCornerBad || secondCornerBad) && this._endsWithAWall) {
        return false;
    }

    return true;
}

/**
 * @param {function} digCallback Dig callback with a signature (x, y, value). Values: 0 = empty.
 */
ROT.Map.Feature.Corridor.prototype.create = function (digCallback) {
    var sx = this._startX;
    var sy = this._startY;
    var dx = this._endX - sx;
    var dy = this._endY - sy;
    var length = 1 + Math.max(Math.abs(dx), Math.abs(dy));

    if (dx) {
        dx = dx / Math.abs(dx);
    }
    if (dy) {
        dy = dy / Math.abs(dy);
    }
    var nx = dy;
    var ny = -dx;

    for (var i = 0; i < length; i++) {
        var x = sx + i * dx;
        var y = sy + i * dy;
        digCallback(x, y, 0);
    }

    return true;
}

ROT.Map.Feature.Corridor.prototype.createPriorityWalls = function (priorityWallCallback) {
    if (!this._endsWithAWall) {
        return;
    }

    var sx = this._startX;
    var sy = this._startY;

    var dx = this._endX - sx;
    var dy = this._endY - sy;
    if (dx) {
        dx = dx / Math.abs(dx);
    }
    if (dy) {
        dy = dy / Math.abs(dy);
    }
    var nx = dy;
    var ny = -dx;

    priorityWallCallback(this._endX + dx, this._endY + dy);
    priorityWallCallback(this._endX + nx, this._endY + ny);
    priorityWallCallback(this._endX - nx, this._endY - ny);
}
/**
 * @class Base noise generator
 */
ROT.Noise = function () {
};

ROT.Noise.prototype.get = function (x, y) {
}
/**
 * A simple 2d implementation of simplex noise by Ondrej Zara
 *
 * Based on a speed-improved simplex noise algorithm for 2D, 3D and 4D in Java.
 * Which is based on example code by Stefan Gustavson (stegu@itn.liu.se).
 * With Optimisations by Peter Eastman (peastman@drizzle.stanford.edu).
 * Better rank ordering method by Stefan Gustavson in 2012.
 */

/**
 * @class 2D simplex noise generator
 * @param {int} [gradients=256] Random gradients
 */
ROT.Noise.Simplex = function (gradients) {
    ROT.Noise.call(this);

    this._F2 = 0.5 * (Math.sqrt(3) - 1);
    this._G2 = (3 - Math.sqrt(3)) / 6;

    this._gradients = [
        [ 0, -1],
        [ 1, -1],
        [ 1, 0],
        [ 1, 1],
        [ 0, 1],
        [-1, 1],
        [-1, 0],
        [-1, -1]
    ];

    var permutations = [];
    var count = gradients || 256;
    for (var i = 0; i < count; i++) {
        permutations.push(i);
    }
    permutations = permutations.randomize();

    this._perms = [];
    this._indexes = [];

    for (var i = 0; i < 2 * count; i++) {
        this._perms.push(permutations[i % count]);
        this._indexes.push(this._perms[i] % this._gradients.length);
    }

};
ROT.Noise.Simplex.extend(ROT.Noise);

ROT.Noise.Simplex.prototype.get = function (xin, yin) {
    var perms = this._perms;
    var indexes = this._indexes;
    var count = perms.length / 2;
    var G2 = this._G2;

    var n0 = 0, n1 = 0, n2 = 0, gi; // Noise contributions from the three corners

    // Skew the input space to determine which simplex cell we're in
    var s = (xin + yin) * this._F2; // Hairy factor for 2D
    var i = ~~(xin + s);
    var j = ~~(yin + s);
    var t = (i + j) * G2;
    var X0 = i - t; // Unskew the cell origin back to (x,y) space
    var Y0 = j - t;
    var x0 = xin - X0; // The x,y distances from the cell origin
    var y0 = yin - Y0;

    // For the 2D case, the simplex shape is an equilateral triangle.
    // Determine which simplex we are in.
    var i1, j1; // Offsets for second (middle) corner of simplex in (i,j) coords
    if (x0 > y0) {
        i1 = 1;
        j1 = 0;
    } else { // lower triangle, XY order: (0,0)->(1,0)->(1,1)
        i1 = 0;
        j1 = 1;
    } // upper triangle, YX order: (0,0)->(0,1)->(1,1)

    // A step of (1,0) in (i,j) means a step of (1-c,-c) in (x,y), and
    // a step of (0,1) in (i,j) means a step of (-c,1-c) in (x,y), where
    // c = (3-sqrt(3))/6
    var x1 = x0 - i1 + G2; // Offsets for middle corner in (x,y) unskewed coords
    var y1 = y0 - j1 + G2;
    var x2 = x0 - 1 + 2 * G2; // Offsets for last corner in (x,y) unskewed coords
    var y2 = y0 - 1 + 2 * G2;

    // Work out the hashed gradient indices of the three simplex corners
    var ii = i.mod(count);
    var jj = j.mod(count);

    // Calculate the contribution from the three corners
    var t0 = 0.5 - x0 * x0 - y0 * y0;
    if (t0 >= 0) {
        t0 *= t0;
        gi = indexes[ii + perms[jj]];
        var grad = this._gradients[gi];
        n0 = t0 * t0 * (grad[0] * x0 + grad[1] * y0);
    }

    var t1 = 0.5 - x1 * x1 - y1 * y1;
    if (t1 >= 0) {
        t1 *= t1;
        gi = indexes[ii + i1 + perms[jj + j1]];
        var grad = this._gradients[gi];
        n1 = t1 * t1 * (grad[0] * x1 + grad[1] * y1);
    }

    var t2 = 0.5 - x2 * x2 - y2 * y2;
    if (t2 >= 0) {
        t2 *= t2;
        gi = indexes[ii + 1 + perms[jj + 1]];
        var grad = this._gradients[gi];
        n2 = t2 * t2 * (grad[0] * x2 + grad[1] * y2);
    }

    // Add contributions from each corner to get the final noise value.
    // The result is scaled to return values in the interval [-1,1].
    return 70 * (n0 + n1 + n2);
}

/**
 * @class Abstract pathfinder
 * @param {int} toX Target X coord
 * @param {int} toY Target Y coord
 * @param {function} passableCallback Callback to determine map passability
 * @param {object} [options]
 * @param {int} [options.topology=8]
 */
ROT.Path = function (toX, toY, passableCallback, options) {
    this._toX = toX;
    this._toY = toY;
    this._fromX = null;
    this._fromY = null;
    this._passableCallback = passableCallback;
    this._options = {
        topology:8
    }
    for (var p in options) {
        this._options[p] = options[p];
    }

    this._dirs = ROT.DIRS[this._options.topology];
}

/**
 * Compute a path from a given point
 * @param {int} fromX
 * @param {int} fromY
 * @param {function} callback Will be called for every path item with arguments "x" and "y"
 */
ROT.Path.prototype.compute = function (fromX, fromY, callback) {
}

ROT.Path.prototype._getNeighbors = function (cx, cy) {
    var result = [];
    for (var i = 0; i < this._dirs.length; i++) {
        var dir = this._dirs[i];
        var x = cx + dir[0];
        var y = cy + dir[1];

        if (!this._passableCallback(x, y)) {
            continue;
        }
        result.push([x, y]);
    }

    return result;
}
/**
 * @class Simplified Dijkstra's algorithm: all edges have a value of 1
 * @augments ROT.Path
 * @see ROT.Path
 */
ROT.Path.Dijkstra = function (toX, toY, passableCallback, options) {
    ROT.Path.call(this, toX, toY, passableCallback, options);

    this._computed = {};
    this._todo = [];
    this._add(toX, toY, null);
}
ROT.Path.Dijkstra.extend(ROT.Path);

/**
 * Compute a path from a given point
 * @see ROT.Path#compute
 */
ROT.Path.Dijkstra.prototype.compute = function (fromX, fromY, callback) {
    var key = fromX + "," + fromY;
    if (!(key in this._computed)) {
        this._compute(fromX, fromY);
    }
    if (!(key in this._computed)) {
        return;
    }

    var item = this._computed[key];
    while (item) {
        callback(item.x, item.y);
        item = item.prev;
    }
}

/**
 * Compute a non-cached value
 */
ROT.Path.Dijkstra.prototype._compute = function (fromX, fromY) {
    while (this._todo.length) {
        var item = this._todo.shift();
        if (item.x == fromX && item.y == fromY) {
            return;
        }

        var neighbors = this._getNeighbors(item.x, item.y);

        for (var i = 0; i < neighbors.length; i++) {
            var neighbor = neighbors[i];
            var x = neighbor[0];
            var y = neighbor[1];
            var id = x + "," + y;
            if (id in this._computed) {
                continue;
            }
            /* already done */
            this._add(x, y, item);
        }
    }
}

ROT.Path.Dijkstra.prototype._add = function (x, y, prev) {
    var obj = {
        x:x,
        y:y,
        prev:prev
    }
    this._computed[x + "," + y] = obj;
    this._todo.push(obj);
}
/**
 * @class Simplified A* algorithm: all edges have a value of 1
 * @augments ROT.Path
 * @see ROT.Path
 */
ROT.Path.AStar = function (toX, toY, passableCallback, options) {
    ROT.Path.call(this, toX, toY, passableCallback, options);

    this._todo = [];
    this._done = {};
    this._fromX = null;
    this._fromY = null;
}
ROT.Path.AStar.extend(ROT.Path);

/**
 * Compute a path from a given point
 * @see ROT.Path#compute
 */
ROT.Path.AStar.prototype.compute = function (fromX, fromY, callback) {
    this._todo = [];
    this._done = {};
    this._fromX = fromX;
    this._fromY = fromY;
    this._add(this._toX, this._toY, null);

    while (this._todo.length) {
        var item = this._todo.shift();
        if (item.x == fromX && item.y == fromY) {
            break;
        }
        var neighbors = this._getNeighbors(item.x, item.y);

        for (var i = 0; i < neighbors.length; i++) {
            var neighbor = neighbors[i];
            var x = neighbor[0];
            var y = neighbor[1];
            var id = x + "," + y;
            if (id in this._done) {
                continue;
            }
            this._add(x, y, item);
        }
    }

    var item = this._done[fromX + "," + fromY];
    if (!item) {
        return;
    }

    while (item) {
        callback(item.x, item.y);
        item = item.prev;
    }
}

ROT.Path.AStar.prototype._add = function (x, y, prev) {
    var obj = {
        x:x,
        y:y,
        prev:prev,
        g:(prev ? prev.g + 1 : 0),
        h:this._distance(x, y)
    }
    this._done[x + "," + y] = obj;

    /* insert into priority queue */

    var f = obj.g + obj.h;
    for (var i = 0; i < this._todo.length; i++) {
        var item = this._todo[i];
        if (f < item.g + item.h) {
            this._todo.splice(i, 0, obj);
            return;
        }
    }

    this._todo.push(obj);
}

ROT.Path.AStar.prototype._distance = function (x, y) {
    switch (this._options.topology) {
        case 4:
            return (Math.abs(x - this._fromX) + Math.abs(y - this._fromY));
            break;

        case 6:
            var dx = Math.abs(x - this._fromX);
            var dy = Math.abs(y - this._fromY);
            return dy + Math.max(0, (dx - dy) / 2);
            break;

        case 8:
            return Math.max(Math.abs(x - this._fromX), Math.abs(y - this._fromY));
            break;
    }
}
